"""
题目：https://leetcode-cn.com/problems/merge-k-sorted-lists/
    给你一个链表数组，每个链表都已经按升序排列。
    请你将所有链表合并到一个升序链表中，返回合并后的链表。
    示例 1：
    输入：lists = [[1,4,5],[1,3,4],[2,6]]
    输出：[1,1,2,3,4,4,5,6]
    解释：链表数组如下：
    [
    1->4->5,
    1->3->4,
    2->6
    ]
    将它们合并到一个有序链表中得到。
    1->1->2->3->4->4->5->6
思路：按照顺序排序链表。先设置一个最终链表rst，让其虚拟头结点为最小值，然后合并rst与输入lists中的每一个链表即可。
时间复杂度：O(k^2 * n)
空间复杂度：O(1)
"""
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        rst = ListNode(float('-inf'))
        for lst in lists:
            rst = self.merge2List(rst,lst)
        return rst.next

    def merge2List(self,l1,l2):
        pre = ListNode()
        cur = pre
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        if l1:
            cur.next = l1
        if l2:
            cur.next = l2
        return pre.next
        